package main.java.indi.zyj.sword;

public class CountTarget {

    public int countTarget(int[] scores, int target) {

        int low = 0, high = scores.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (scores[mid] > target) {
                high = mid - 1;
            } else if (scores[mid] < target) {
                low = mid + 1;
            } else {
                if (scores[low] == scores[high]) {
                    return high - low + 1;
                }
                if (scores[low] < target) {
                    low++;
                }
                if (scores[high] > target) {
                    high--;
                }
            }
        }

        return 0;

    }


    public int countTarget1(int[] scores, int target) {

        // 搜索右边界 right 相等时m+1探索右边界
        int i = 0, j = scores.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(scores[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;

        // 若数组中无 target ，则提前返回
        if(j >= 0 && scores[j] != target) return 0;


        // 搜索左边界 left 相等时m-1探索左边界
        i = 0; j = scores.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(scores[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;

        return right - left - 1;
    }

    /**
     * @Description     找到target和target-1的右边界，相减
     * @param scores
     * @param target
     * @return int
     * @author zyj
     * @date 2024/05/09 16:40
     */
    public int countTarget2(int[] scores, int target) {
        return helper(scores, target) - helper(scores, target - 1);
    }

    public int helper(int[] scores, int target) {
        int low = 0, high = scores.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (scores[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

}
